1. Field of the Invention
This invention relates generally to transmission of compressed digital information having a constant time delay constraint over a transmission system having an effective transmission bit-rate which may vary, and more particularly to management of buffer storage and control of variable bit-rates in such systems.
2. Description of the Related Art
Currently there is much interest in creating systems which can efficiently deliver digital video on electrical or optical transmission lines into homes and businesses. Delivery of video movies to customers on demand is one application. Another is interactive home television. The so-called digital information superhighway concept includes the notion that video signals will be efficiently delivered just as telephone signals are today.
To do this, video data must be compressed (usually called encoded) before transmission to a destination and then decompressed (usually called decoded) at the destination for display. FIG. 1 shows a typical prior art system. A digital video input signal 10 is compressed by encoder 12, transmitted to a destination site by a communication network 14, and decompressed by a decoder 16 to produce an output digital video signal 18.
One requirement that real time transmission of video information imposes is that the encoded information for each successive video frame must be available for decoding and display at the destination when needed. If the encoded information for a video frame is not available at the decoder when it is needed, a video frame (or part of a frame) cannot be produced for display and video quality will be degraded. Once display of a video sequence is started at the receiver, a time delay is established between the compression process at the encoder and the decompression process at the decoder. This time delay must remain constant if there are to be no freeze frames or skipped frames. Herein, this will be called the constant time delay constraint.
A constant time delay is made possible by anticipating variation in bit rate flow and accommodating it with buffering. The buffers must be partly filled so they can accept or deliver bits as required to accommodate anticipated bit rate flow variations. Appropriate time delay is introduced so that the buffers become suitably filled partially as desired before bits are released to the decoder for display.
One source of bit rate flow variation is in the encoder itself. Efficient compression (or encoding) algorithms (including the ones used in the widely accepted MPEG-1 and MPEG-2 standards created by the Moving Pictures Experts Group) do not compress (or encode) digital information at a constant compression ratio. In systems of this type, not every pixel, block, macroblock or frame of video is compressed to the same number of bits. Thus the number of bits produced by an encoder of this kind in a unit of time varies with time. The compression ratio (i.e., ratio of input bits to output bits) resulting from use of such algorithms typically varies with the content of the digital information being compressed. Encoders of this type which produce an output bit flow that is not uniform are said to do "variable-rate encoding". Any real time video transmission capability that meets the MPEG standard must accommodate this variation in the rate at which bits are generated by the MPEG compression (or encoding) algorithms. Typically this is done by providing buffer storage at the encoder (i.e., buffer 20 in FIG. 1) and at the decoder (i.e., buffer 22 in FIG. 1). In such a system, bits may leave the encoder buffer at a constant rate (even in the presence of such variable-rate encoding), so encoders of this kind are called constant output-rate encoders.
A second source of bit rate flow variation is the communication system. In reality, even for constant output-rate encoders, the communication system is usually multiplexed in some fashion, so groups of bits (rather than individual bits) actually leave the encoder buffer at a uniform rate. This does not necessarily mean, however, that groups of bits entering the communication system at a uniform rate also will be delivered by the communication system to a destination at a uniform rate. Whenever the communication system employs packetizing or there is any remultiplexing or switching of digital streams in the communication system, data groups experience variable delays in transmission time and data groups arrive at the decoder buffer in a bursty fashion.
A typical transmission system is shown in FIG. 1. Encoder buffer 20 becomes the source of data stream S.sub.1. A multiplexer 24 multiplexes a plurality of source data streams S.sub.1 -S.sub.3 according to a packet scheduling algorithm to generate one multiplexed bit-stream D.sub.1. This bit-stream is then transmitted over the transmission facility 14, which typically includes a number of remultiplexing or packet switching nodes 26, 28 and a demultiplexer 30 serving decoder 16. Bit-stream D.sub.1 does not remain in the same multiplexed format all the way to demultiplexer 30. At remultiplexing or packet switching stage 26, for example, one or more additional source data streams S.sub.4 might be added, and one or more additional bit-streams D.sub.2 might be added as well. Also, the output from this stage might be divided into two or more output bit-streams D.sub.3, D.sub.4, and one or more demultiplexed individual data streams (such as S.sub.2 as shown) might be output as well. It is assumed that the S.sub.1 data stream is contained in multiplexed output bit-stream D.sub.3, which enters another remultiplexing or packet switching node 28. Additional bit-streams D.sub.5, D.sub.6 might be added at this stage and bit-streams D.sub.7 -D.sub.9 might depart. Bit-stream D.sub.9 is assumed to contain data stream S.sub.1 and enters demultiplexer 30, which reproduces data stream S.sub.1.
It is important to note that while the output data stream S.sub.1 contains the same packets of data that entered the communication network and in the same order, the time spacing of the packets generally has been altered because the relative locations of individual packets are altered when D.sub.1 is converted into D.sub.3 and D.sub.3 is converted into D.sub.9. The specific kind of transmission network is not important. However, it is important to understand that the kinds of transmission facilities described will necessarily include some buffer storage to accommodate remultiplexing or packet switching. Data packets cannot become displaced relative to each other unless there is some buffer storage to hold the data packets while relative displacement occurs. In FIG. 2 this buffering is generally represented as buffers 32. This network buffer storage is not taken into account in the conventional model for encoding systems.
Additional complexity arises in satisfying the constant time delay constraint when the transmission system itself contains buffer storage in addition to the buffer storage at the encoder and at the decoder. The encoder and decoder buffers cannot be permitted to overflow (since this would result in loss of data and produce a skip frame error) and the decoder buffer (at least) cannot be permitted to underflow (i.e., not have stored bits when stored bits are needed for decompression) because this will produce a freeze frame error.
It becomes even more complex to guarantee the constant time delay constraint if the average bit-rate at which an encoder operates can vary over time. Such encoders are called "variable output-rate" encoders. Encoders of this type are used, for example, in order to support joint bit-rate control or statistical multiplexing. These systems are desirable because it is generally better to allow the transmission bandwidth allotted to existing active communication links or channels in a network to be degraded (i.e., continue at a reduced bandwidth) when necessary rather than have some of them terminated. Also, much more sophisticated network management can be implemented if the bandwidth (i.e., bit-rate allotted to each link or channel) can be increased and decreased.
Variable output-rate encoding cannot be accommodated merely by providing additional buffer storage, at least not buffer storage of a reasonable size. A change in the average bit-rate at which the encoder is operating requires a corresponding change in the transmission channel-rate that the communication system allots to this encoder. However, synchronization of the two bit-rate changes is not required if there is adequate buffering to cover the asynchrony.
MPEG standards were not designed to accommodate variable output-rate encoding. Furthermore, the MPEG standards have specified the decoder in great detail, including the size of the decoder buffer. This was done because it is anticipated that there will be very many decoders and very few encoders in a typical system. In an on-demand video system, for example, there will be a decoder in each customer's home or business and only one encoder at the supplier of the on-demand video service. Buffer storage is too costly to place any more of it than necessary at each decoder. Therefore, the MPEG Committee specified the size of the decoder buffer in the MPEG-1 and MPEG-2 standards and these standards have been widely accepted. MPEG-2, for example, specifies that the decoder buffer will be 1.75 MB and allows transmission rates of up to 15 MB. This buffer size equals about 1.2 second of storage at a 1.5 MB transmission rate and only about 0.12 seconds of storage at a 15 MB transmission rate.
While the MPEG Committee specified the decoder in great detail (and assumed a constant bit-rate system), the encoder was left substantially unspecified (except of course that it must provide data compressed in a specified manner). If variable bit-rate operation is desired in a video transmission system which uses decoders that meet the MPEG-1 or MPEG-2 standard, the encoder must be designed somehow to accommodate the bit-rate variation without involvement from the decoder and without changing the fixed decode buffer size specified by the MPEG standards.